package KMP;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class method {
    //next数组
    public static int[] next = new int[105];
    //记录匹配成功下标集合list
    public static List<Integer> list = new ArrayList<>();

    public static void main(String[] args) {
        String s1, s2;
        Scanner sc = new Scanner(System.in);
        s1 = sc.next();
        s2 = sc.next();
        int len1 = s1.length();
        int len2 = s2.length();

        //如果有任意字符串为空串则可以结束匹配
        if (len1 == 0 || len2 == 0) {
            System.out.println("失配");
            return;
        }

        //获得next数组
        getNext(s2);

        //i和j相当于字符串s1和s2的指针
        int i = 0, j = 0;

        while (i < len1 && j < len2) {
            if (j == -1 || s1.charAt(i) == s2.charAt(j)) {
                //如果位置匹配或需要重新匹配指针都要往前走
                i++;
                j++;
            } else {
                j = next[j];
            }
            //如果模式串匹配成功记录下标回退匹配
            if (j == len2) {
                list.add(i - len2 + 1);
                j = next[j];
            }
        }

        //输出匹配成功的下标
        list.forEach(System.out::println);

        System.out.println("next:");
        //输出模式串
        for (int k = 0; k <= len2; k++) {
            System.out.print(next[k] + " ");
        }
    }

    /**
     * 获得next数组
     *
     * @param s
     */
    public static void getNext(String s) {
        int len = s.length();

        //注意初始要把next数组设为-1，可以想想为什么
        next[0] = -1;
        int i = 1, j = 0;

        //正常可以<len-1就跳出循环，因为nex[len]是一定用不到的
        //这里主要为了一会输出展示next数组才循环到len
        while (i < len) {
            if (j == -1 || s.charAt(i) == s.charAt(j)) {
                next[++i] = ++j;
            } else {
                j = next[j];
            }
        }
    }
}


/*
* 这里再提供一组测试数据，读者可自行实现代码后用以自测
*
* 测试数据：
122345689515652235656
22
* 输出：
2
15
next:
-1 0 1
* */